package 笔试;

import java.util.ArrayList;
import java.util.HashMap;

public class 腾讯音乐_带重复节点的前序中序二叉树 {
    public ArrayList<TreeNode> list = new ArrayList<>();
    public HashMap<Integer, Integer> map;
    int index = 0;
    boolean[] flag;
    public ArrayList<TreeNode> getBinaryTrees (ArrayList<Integer> preOrder, ArrayList<Integer> inOrder) {
        map = new HashMap<Integer, Integer>();
        flag = new boolean[preOrder.size()];
        for (int i = 0; i < preOrder.size(); i++) {
            map.put(preOrder.get(i), map.getOrDefault(preOrder.get(i), 0) + 1);
        }

        list.add(bulidTreeInternal(preOrder, inOrder, 0, inOrder.size()));
        return list;
    }

    private TreeNode bulidTreeInternal(ArrayList<Integer> preOrder, ArrayList<Integer> inOrder, int l, int r) {
        if (l >= r) {
            return null;
        }
        if(index >= preOrder.size()) {
            return null;
        }


        TreeNode root = new TreeNode(preOrder.get(index));
        index++;

        int pos = find(inOrder, l, r, root.val);
        if(index+1 < preOrder.size() && preOrder.get(index) == preOrder.get(index+1)) {
            int f = 1;
            for (int i = 0; i < 2; i++) {
                if(f == 1) {
                    root.left = bulidTreeInternal(preOrder, inOrder, l, pos);
                    root.right = bulidTreeInternal(preOrder, inOrder, pos+1, r);

                    f = 2;
                } else {
                    root.right = bulidTreeInternal(preOrder, inOrder, pos+1, r);
                    root.left = bulidTreeInternal(preOrder, inOrder, l, pos);
                }
            }

        } else {
            root.left = bulidTreeInternal(preOrder, inOrder, l, pos);
            root.right = bulidTreeInternal(preOrder, inOrder, pos+1, r);
        }
        return root;
    }

    private int find(ArrayList<Integer> inOrder, int l, int r, int val) {
        for (int i = l; i < inOrder.size(); i++) {
            if (inOrder.get(i) == val) {
                return i;
            }
        }
        return -1;
    }



}
